A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets. The packets are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
Routing devices within a network, often referred to as routers, maintain routing information that describes available routes through the network. Upon receiving an incoming packet, the router examines information within the packet and forwards the packet in accordance with the routing information. In order to maintain an accurate representation of the network, routers exchange routing information in accordance with one or more defined routing protocol, such as the Border Gateway Protocol (BGP).
The term “link” is often used to refer to the connection between two devices on a network. The link may be a physical medium, such as a copper wire, a coaxial cable, any of a host of different fiber optic lines or a wireless connection. In addition, network devices may define “virtual” or “logical” links, and map the virtual links to the physical links
Packet-based computer networks increasingly utilize label switching protocols for traffic engineering and other purposes. Multi-Protocol Label Switching (MPLS) is a mechanism used to engineer traffic patterns within Internet Protocol (IP) networks. MPLS may be viewed as a protocol that allows packet-based networks to emulate certain properties of a circuit-switched network. By utilizing MPLS, a source device can request a path through a network to a destination device, i.e., a Label Switched Path (LSP). An LSP defines a distinct path through the network to carry MPLS packets from the source device to a destination device. Each router along an LSP allocates a label and propagates the label to the closest upstream router along the path for use in forwarding MPLS packets along the path. Routers along the path cooperatively perform MPLS operations to forward the MPLS packets along the established path.
Routers at the beginning of the LSP are commonly known as ingress routers, while routers at the end of the LSP are commonly known as egress routers. Ingress and egress routers as well as intermediate routers along the LSP that support MPLS are more generally referred to as label switching routers (LSRs). A set of packets to be forwarded along the LSP is referred to as a forwarding equivalence class (FEC). A plurality of FECs may exist for each LSP, but there may be only one active LSP for any given FEC. Typically, a FEC definition includes the IP address of the destination of the LSP. The ingress label edge router (LER) uses routing information, propagated from the egress LER, to determine the LSP, to assign labels for the LSP, and to affix a label to each packet of the FEC. The LSRs utilize MPLS protocols to receive MPLS label mappings from downstream LSRs and to advertise MPLS label mappings to upstream LSRs. When an LSR receives an MPLS packet from an upstream router, it switches the MPLS label according to the information in its forwarding table and forwards the packet to the appropriate downstream LSR or LER. The egress LER removes the label from the packet and forwards the packet to its destination in accordance with standard routing protocols.
In general, each router along the LSP maintains a context that associates a FEC with an incoming label and an outgoing label. In this manner, when an LSR receives a labeled packet, the LSR may swap the label (i.e., the incoming label) with the outgoing label by performing a lookup in the context. The LSR may then forward the packet to the next LSR or LER along the LSP. The next router along the LSP is commonly referred to as a downstream router or a next hop.
In some instances, a router along an LSP may no longer be available. For example, the router may experience a failure event, such as when one or more components of the router fail, the router is brought down by a user, such as a network operator, or a link along the LSP coupled to the router fails. The router may be brought down by the network operator for a variety of reasons, such as when the router requires servicing in the form of a software, hardware, or firmware upgrade, or for other reasons. Routers along the LSP may implement an automatic corrective scheme to avoid a router that is no longer available. MPLS fast reroute, also known as MPLS local protection, is one scheme that routers implement to automatically correct instances of router or link failure. In accordance with MPLS fast reroute, each router along an LSP allocates a backup path to reach the egress router, such that the backup path utilizes a different next hop along a different link. When a router along an LSP is no longer available, the upstream router thereof (known as the point of local repair, or PLR) forwards traffic of the LSP along the backup path to reach the egress router of the LSP. There is currently no automatic corrective scheme to repair an LSP in the case that the egress router itself is unavailable.